/*
* 生成凸包
*/

// 极角排序
const {randomIntFromRange} = require("./utils");

function point_sort(a, b) {
    if (a[0] < b[0]) return -1
    else if (a[0] === b[0]) {
        if (a[1] < b[1]) return -1
        return 1
    } else return 1
}

// 叉积
function cross(a, b) {
    return a[0] * b[1] - a[1] * b[0]
}

// 点减法
function sub(a, b) {
    return [a[0] - b[0], a[1] - b[1]]
}

/*
points: 长度为n的size为2的数组
n: points长度
return: [凸包点列表，凸包点个数]
*/
function convex_hull(points, n) {
    points.sort(point_sort)
    let m = 0;
    const ch = [];
    for (let i = 0; i < n; i++) {
        while (m > 1 && cross(sub(ch[m - 1], ch[m - 2]), sub(points[i], ch[m - 1])) <= 0)
            m--;
        ch[m] = points[i];
        m++;
    }
    let k = m;
    for (let i = n - 2; i >= 0; i--) {
        while (m > k && cross(sub(ch[m - 1], ch[m - 2]), sub(points[i], ch[m - 1])) <= 0)
            m--;
        ch[m] = points[i];
        m++;
    }
    if (n > 1)
        m--;
    return [ch, m];
}

function generatePolygon(x, y, weight, height, state) {
    if (state === 'up') {
        return generateUpPolygon(x, y, weight, height);
    }
    if (state === 'down') return generateDownPolygon(x, y, weight, height);
    return generateConvexPolygon(x, y, weight, height, [], 0);
}

function generateUpPolygon(x, y, weight, height) {
    let points = [];
    points[0] = [x + weight / 3, y];
    points[1] = [x + weight * 2 / 3, y];
    points[2] = [x + weight / 2, y + height];
    return generateConvexPolygon(x, y, weight, height, points, 3);
}

function generateDownPolygon(x, y, weight, height) {
    let points = [];
    points[0] = [x + weight / 3, y + height];
    points[1] = [x + weight * 2 / 3, y + height];
    points[2] = [x + weight / 2, y];
    return generateConvexPolygon(x, y, weight, height, points, 3);
}

function generateConvexPolygon(x, y, weight, height, points, n) {
    let pointsNumber = randomIntFromRange(3, 10);

    for (let i = 0; i < pointsNumber; ++i) {
        points[i + n] = [x + randomIntFromRange(0, weight), y + randomIntFromRange(0, height)];
    }
    return convex_hull(points, pointsNumber + n);
}

module.exports = {
    convex_hull,
    generateConvexPolygon,
    generateUpPolygon,
    generateDownPolygon,
    generatePolygon
};

/*
a = [[0, 0], [3, 0], [0, 3], [1, 1], [0, 0.5]]
res = convex_hull(a, 5)
console.log(res[0])
console.log(res[1])
*/